package com.cn.algorithm01;

/**
 * @author hels
 * @version 1.0
 * @date 2021/10/13 9:52
 */
public class Code07_LinkedList {

    public static void main(String[] args) {
        Node n1 = new Node(1);
        n1.next = new Node(2);
        n1.next.next = new Node(3);

        n1 = reverseSingle(n1);
        //单项链表反转验证
//        while (n1 != null) {
//            System.out.print(n1.value + " ");
//            n1 = n1.next;
//        }

        System.out.println("=====双向链表====");
        DoubleNode d1 = new DoubleNode(1);
        d1.next = new DoubleNode(2);
        d1.next.next = new DoubleNode(3);
        d1.next.last = d1;
        d1.next.next.last = d1.next;

        System.out.println("反转前：");
//        while (d1 != null) {
//            System.out.print(d1.value + " ");
//            d1 = d1.next;
//            if (d1.value == 3) {
//                System.out.println(d1.value);
//                while (d1 != null) {
//                    System.out.print(d1.value + " ");
//                    d1 = d1.last;
//                }
//            }
//        }
        System.out.println();
        d1 = reverseDouble(d1);
        System.out.println("反转后：" + d1.value);
        // 双向链表反转验证
        while (d1 != null) {
            System.out.print(d1.value + " ");
            d1 = d1.next;
            if (d1.value == 1) {
                System.out.println(d1.value);
                while (d1 != null) {
                    System.out.print(d1.value + " ");
                    d1 = d1.last;
                }
            }
        }

    }

    //内部类：单链表
    public static class Node {
        public int value;
        public Node next;

        public Node(int data) {
            this.value = data;
        }
    }

    //内部类：双链表
    public static class DoubleNode {
        public int value;
        public DoubleNode last;
        public DoubleNode next;

        public DoubleNode(int data) {
            value = data;
        }
    }

    // 翻转单链表
    public static Node reverseSingle(Node head) {
        Node pre = null;
        Node next = null;

        while (head != null) {
            next = head.next;
            head.next = pre;
            pre = head;
            head = next;
        }

        return pre;
    }

    //翻转双链表
    public static DoubleNode reverseDouble(DoubleNode head) {
        DoubleNode pre = null;
        DoubleNode next = null;

        while (head != null) {
            next = head.next;
            head.next = pre;
            head.last = next;
            pre = head;
            head = next;
        }
        System.out.println("反转后的值：" + pre.value);


        return pre;
    }

}
